粉刷房子 III
在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n）。有的房子去年夏天已经涂过颜色了，所以这些房子不需要被重新涂色。
我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）
给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：
houses[i]：是第i个房子的颜色，0表示这个房子还没有被涂色。cost[i][j]：是将第i个房子涂成颜色j+1的花费。
请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。
示例1：
输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：9
解释：房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。
示例 2：
输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。
示例 3：
输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5
示例 4：
输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。
分析
- 先通过
houses和target和n, 分割出可行的街区方案 - 遍历并计算每一种方案的花费
- 输出最小的花费
代码
借助深度优先，找出所有可行的切割方案，然后再求出方案花费，计算最小值
var minCost = function(houses, cost, m, n, target) {
let targetStree = []
// dp 使用递归方式 求出 所有的分割方式
// 上一个房子颜色， 此时街区的数量, 遍历到的位置
const resDfs = (houseColor, k, postion, res)=>{
// 此时的颜色
if(postion > houses.length) return
if(k > target) return
if(k + position < houses.length) return
if(postion === houses.length && k === target){
targetStree.push([...res])
}
if(houses[postion] !== 0){
res.push(houses[postion])
if(houseColor === houses[postion]) resDfs(houses[postion],k,postion+1,res)
else resDfs(houses[postion],k+1,postion+1,res)
res.pop()
}else{
for(let i=1;i<=n;i++){
res.push(i)
if(i === houseColor) resDfs(i,k,postion+1,res)
else resDfs(i,k+1,postion+1,res)
res.pop()
}
}
}
if(houses[0] === 0 ){
let res = []
for(let i=1;i<=n;i++){
res.push(i)
resDfs(i,1,1,res)
res.pop()
}
}
else resDfs(houses[0],1,1,[houses[0]])
if(targetStree.length === 0) return -1
let resArray = targetStree.map(item => item.reduce((a,b,index)=>{
if(houses[index] === 0){
a += cost[index][b-1]
}
return a
}, 0)
)
return Math.min(...resArray)
};
算法的时间复杂度和空间复杂度都是(O(nn)), 在数据量比较庞大时，会出现堆栈溢出的情况，所以将递归调用转化成for循环来调用。
官方题解 动态规划
为了方便编码和叙述:
- 房子的编号为 [0, m-1]；
- 颜色的编号为 [0, n-1]，如果房子没有涂上颜色，那么记为 -1；
- 街区的编号为 [0, target−1]。
设 dp(i,j,k) 表示将 [0,i] 的房子都涂上颜色，最末尾的第 i 个房子的颜色为 j，并且它属于第 k 个街区时，需要的最少花费。
状态变换方程
当 i-1 个房子的颜色为j0
- 如果 house[i] !== -1, 说明第 i 个房子已经涂过颜色了, 那 houses[i] === j
- 当 house[i] !== j,则说明是无效的状态 dp[i][j][k] = ∞
- 当 house[i] === j
- 如果 j === j0, 则属于一个街区, dp[i][j][k] = dp[i-1][j][k]
- 如果 j !== j0, 则不属于一个街区, dp[i][j][k] = min(dp[i-1][j0][k-1])
- 如果 house[i] === -1, 说明第i个房子未涂色, 如果涂上j, 则为 cost[i][j]
- 如果 j === j0, 则属于一个街区, dp[i][j][k] = dp[i-1][j][k] + cost[i][j]
- 如果 j !==j0, 则不属于一个街区, dp[i][j][k] = min(dp[i-1][j0][k-1]) + cost[i][j]
最终的答案是: min(dp[m-1][j][target-1])
var minCost = function(houses, cost, m, n, target) {
houses = houses.map(item => --item)
const dp = new Array(m).fill(0)
.map(() => new Array(n).fill(0)
.map(() => new Array(target).fill(Number.MAX_VALUE)));
// house i 的 循环
for(let i=0;i<m;i++){
// color j 的 循环
for(let j=0;j<n;j++){
// 如何记录 分区
if(houses[i] !== -1 && houses[i] !== j) continue
// 记录每一个 dp(i,j,k) 的 值
// 当 i 出现时, k值 最大能出现 i个
for(let k=0;k<=i;k++){
for(let j0=0;j0<n;j0++){
if(j === j0){
if(i===0){
if(k === 0) dp[i][j][k] = 0
}else{
dp[i][j][k] = Math.min(dp[i][j][k],dp[i-1][j][k])
}
}else if(i>0&&k>0){
dp[i][j][k] = Math.min(dp[i][j][k],dp[i-1][j0][k-1])
}
}
if(dp[i][j][k] !== Number.MAX_VALUE && houses[i] === -1) dp[i][j][k] += cost[i][j]
}
}
}
let ans = Number.MAX_VALUE
for(let i=0;i<n;i++){
if(ans > dp[m-1][i][target-1]) ans = dp[m-1][i][target-1]
}
return ans === Number.MAX_VALUE?-1:ans
};